package com.test;

import java.util.LinkedList;
import java.util.Queue;

public class Bin {

	public static void main(String[] args) {
		Node binTree = getBinTree();

		System.out.println("Preorder: ");
		preOrderirstTraversal(binTree);
		System.out.println("Postorder: ");
		postOrderirstTraversal(binTree);
		System.out.println("Inorder: ");
		inOrderirstTraversal(binTree);
		System.out.println("Levelorder: ");
		breathFirstTraversal(binTree);

	}

	static Queue<Node> breathFirstQueue = new LinkedList<Node>();
	static void breathFirstTraversal(Node subNode){

		if (subNode == null){
			return;
		}

		System.out.println(subNode.data);

		if(subNode.left!= null){
			breathFirstQueue.add(subNode.left);
		}

		if(subNode.right!= null){
			breathFirstQueue.add(subNode.right);
		}

		if(!breathFirstQueue.isEmpty()){
			breathFirstTraversal(breathFirstQueue.remove());
		}

	}

	static void preOrderirstTraversal(Node subNode){

		System.out.println(subNode.data);
		if(subNode.left != null){
			preOrderirstTraversal(subNode.left);
		}

		if(subNode.right != null){
			preOrderirstTraversal(subNode.right);
		}
	}


	static void postOrderirstTraversal(Node subNode){
		if(subNode == null){
			return;
		}

		Node left = subNode.left;
		Node right = subNode.right;

		postOrderirstTraversal(left);
		postOrderirstTraversal(right);   

		System.out.println(subNode.data);
	}

	static void inOrderirstTraversal(Node subNode){
		if(subNode == null){
			return;
		}

		Node left = subNode.left;
		Node right = subNode.right;
		postOrderirstTraversal(left);
		System.out.println(subNode.data);
		postOrderirstTraversal(right);   


	}



	static Node getBinTree(){
		Node root = new Node( 5, null, null);

		Node one = new Node(1, null, null);
		root.left = one;

		Node two = new Node(2, null, null);
		one.right = two;

		Node three = new Node(3, null, null);
		two.right = three;

		Node seven = new Node(7, null, null);
		root.right = seven;

		Node fifteen = new Node(15, null, null);
		seven.right = fifteen;

		Node nine = new Node(9, null, null);
		fifteen.left = nine;

		Node eight = new Node(8, null, null);
		nine.left = eight;

		Node fourteen = new Node(14, null, null);
		nine.right = fourteen;

		Node seven2 = new Node(7, null, null);
		eight.left = seven2;


		return root;
	}
}


class Node{
	int data;
	Node left;
	Node right;

	public Node(int data, Node left, Node right){
		this.data = data;
		this.left = left;
		this.right = right;
	}
}